/**
 * \file
 */
#include "precompiled.hpp"
#include "kfs.hpp"
#include "kfs_allocator.hpp"
#include "kfs_cache.hpp"
#include "kfs_impl.hpp"
#include "kfs_time.hpp"
#include "Exception.hpp"
#include <errno.h>
#include <inttypes.h>
#include <iterator>
#include <string>
#include <vector>

using std::auto_ptr;  using std::distance;  using std::min;
using std::string;  using std::vector;

struct Indirection
{
    /// Index into the block table.
    uint16_t tableIndex;
    /// Disk block number
    block_index_t diskBlockNum;
};

typedef vector<Indirection> Indirections;


void kfs::Impl::file_allocator_grow(CacheRef& inodeRef,
    file_size_t growNumBytes, std::vector<block_index_t>* diskBlockNums)
{
    CacheInode& inodeNode = *inodeRef.elt->second;
    Inode& inode = inodeNode.inode;
    file_size_t const newFileSize = inode.sizeNumBytes + growNumBytes;
    block_index_t const oldNumBlocks = (block_index_t)
    div_ceil<file_size_t>(inode.sizeNumBytes, mb.blockNumBytes);
    block_index_t const newNumBlocks = (block_index_t)
    div_ceil<file_size_t>(newFileSize, mb.blockNumBytes);
    if( oldNumBlocks >= newNumBlocks )
    {
        throw Exception("%s: whoops growNumBytes=%"PRIu64, __FUNCTION__,
            growNumBytes);
    }
    block_index_t const growNumBlocks = newNumBlocks - oldNumBlocks;
    boost::scoped_array<uint8_t> block(createBlockBuffer());
    // Prepare the output parameter.
    diskBlockNums->clear();
    diskBlockNums->reserve(growNumBlocks);

    for(block_index_t fBlockNum = oldNumBlocks;
          fBlockNum < newNumBlocks; ++fBlockNum)
    {
        // Add one more block.
        vector<uint32_t> indices;
        file_getIndices(fBlockNum, indices);

        uint32_t* index = & inode.dataBlockAddresses[0];
        uint32_t prevDiskBlockNum = inodeNode.blockNum;

        for(vector<uint32_t>::iterator i = indices.begin();
            i != indices.end();
            ++i
           )
        {
            // Look up the next disk block number in the table.
            uint32_t* tableEntry = index + *i;
            uint32_t nextDiskBlockNum = *tableEntry;
            if(nextDiskBlockNum == 0)
            {
                // Allocate a block to this file (index or data).  We automatically
                // free the block in case of exception.
                AllocBlockRef newBlockRef = disk_allocate();
                nextDiskBlockNum = newBlockRef.get();
                // Add the new block number to the in-memory inode/index table.
                *tableEntry = nextDiskBlockNum;
                // If we updated an index block, write it now.  If we updated the
                // inode, we can ignore it because we will update the inode at the
                // end of the function.
                if(i != indices.begin())
                {
                    kfs_disk_write(*this, prevDiskBlockNum, block.get());
                }
                // Commit the allocation.
                newBlockRef.release();

                // If the new block is an indirect (non-data) block.
                if(distance(i, indices.end()) != 1)
                {
                    // Initialize the block's data and write it.
                    // TODO Consider remote chance of failure here.
                    // TODO Don't do this for a data block. Let the caller decide
                    // whether to write it.
                    memset(block.get(), 0, mb.blockNumBytes);
                    kfs_disk_write( *this, nextDiskBlockNum, block.get() );
                }
            }
            else
            {
                // Load the index block.
                kfs_disk_read(*this, nextDiskBlockNum, block.get());
            }

            // The first lookup is from the inode.  Subsequent lookups are from
            // the index block, which is loaded into block.
            index = reinterpret_cast<uint32_t*>(block.get());

            prevDiskBlockNum = nextDiskBlockNum;
        }
        // Give the caller a pointer on disk to the new data block.
        diskBlockNums->push_back(prevDiskBlockNum);

        // Update the size in the inode.
        if( inode.sizeNumBytes > fBlockNum * mb.blockNumBytes )
        {
            fprintf(stderr, "%s: internal inconsistency in file %u size\n",
                __FUNCTION__, inodeNode.blockNum);
        }

        block_off_t bytesToNextBlock =
        (inode.sizeNumBytes % mb.blockNumBytes)
        ? (mb.blockNumBytes - (block_off_t)(inode.sizeNumBytes % mb.blockNumBytes))
        : (0);
        assert(growNumBytes >= bytesToNextBlock);
        inode.sizeNumBytes += bytesToNextBlock;
        growNumBytes -= bytesToNextBlock;

        block_off_t bytesInNextBlock =
        min<file_size_t>(mb.blockNumBytes, growNumBytes);
        inode.sizeNumBytes += bytesInNextBlock;
        growNumBytes -= bytesInNextBlock;

        assert( inode.sizeNumBytes <= (fBlockNum+1) * mb.blockNumBytes );
        inodeRef.write();
    }

    assert(inode.sizeNumBytes == newFileSize);
    assert(growNumBytes == 0);
}


void kfs::Impl::file_allocator_shrink(CacheRef& inodeRef)
{
    CacheInode& inodeNode = *inodeRef.elt->second;
    if(inodeNode.inode.sizeNumBytes == 0)
    {
        throw Exception("%s: file must not be empty", __FUNCTION__);
    }
    // Compute the indices for the final data block.
    block_index_t const fBlockNum = fileNumBlocks(inodeNode.inode) - 1;
    vector<uint32_t> indices;
    file_getIndices(fBlockNum, indices);

    uint32_t* index = & inodeNode.inode.dataBlockAddresses[0];
    uint32_t prevDiskBlockNum = inodeNode.blockNum;
    boost::scoped_array<uint8_t> block(createBlockBuffer());

    Indirections indirections(indices.size());

    for(size_t i = 0; i < indices.size(); ++i)
    {
        // Populate the Indirection struct.
        indirections[i].tableIndex = indices[i];
        indirections[i].diskBlockNum = prevDiskBlockNum;

        // Look up the next disk block number in the table.
        uint32_t* tableEntry = index + indices[i];
        uint32_t nextDiskBlockNum = *tableEntry;
        if(nextDiskBlockNum == 0)
        {
            throw Exception("Whoops: there is no index entry for file %u block %u",
                inodeNode.blockNum, fBlockNum);
        }

        // Read indirect blocks but not the data block.
        if(i + 1 < indices.size())
        {
            kfs_disk_read(*this, nextDiskBlockNum, block.get());

            // The first lookup is from the Inode structure.  Subsequent
            // lookups are from the index block buffer, "block".
            index = reinterpret_cast<uint32_t*>(block.get());
        }

        prevDiskBlockNum = nextDiskBlockNum;
    }

    // Free the data block.
    disk_free(prevDiskBlockNum);
    bool isChildFreed = true;

    // Inspect each indirect block. If it has no more pointers then free it.
    for(Indirections::reverse_iterator indirect = indirections.rbegin();
        indirect != indirections.rend(); ++indirect)
    {
        // Remove the indirect parent pointer to the freed block.
        if(isChildFreed)
        {
            if(distance(indirect, indirections.rend()) != 1)
            {
                // Read the indirect block from disk.
                kfs_disk_read(*this, indirect->diskBlockNum, block.get());
                // Index into the table.
                index = reinterpret_cast<uint32_t*>(block.get());
            }
            else
            {
                // Reference the in-memory inode.
                index = & inodeNode.inode.dataBlockAddresses[0];
            }
            uint32_t* tableEntry = index + indirect->tableIndex;
            // Remove the pointer to the freed block.
            *tableEntry = 0;
            // Unless this is the inode, then write it now.
            if(distance(indirect, indirections.rend()) != 1)
            {
                // Write the current indirect block to disk.
                kfs_disk_write(*this, indirect->diskBlockNum, block.get());
                // If we have just removed the only entry in this indirect block,
                // then we must also remove this indirect block.
                if(indirect->tableIndex == 0)
                {
                    // Free this indirect block.
                    disk_free(indirect->diskBlockNum);
                }
                else
                {
                    isChildFreed = false;
                }
            }
        }
    }

    // Update the size.  Write the inode.
    inodeNode.inode.sizeNumBytes = fBlockNum * mb.blockNumBytes;
    inodeRef.write();
}


uint32_t
kfs::Impl::file_resolveDiskBlock(CacheRef const& inodeRef, uint32_t fBlockNum)
{
    CacheInode const& inodeNode = *inodeRef.elt->second;
    // Number of data blocks in this file.
    uint32_t const numBlocks = fileNumBlocks(inodeNode.inode);
    if(fBlockNum >= numBlocks)
        throw Exception("File %u has %u data blocks; block %u does not exist",
                inodeNode.blockNum, numBlocks, fBlockNum);

        vector<uint32_t> indices;
    file_getIndices(fBlockNum, indices);

    uint32_t const* index = & inodeNode.inode.dataBlockAddresses[0];

    vector<uint32_t>::const_iterator i = indices.begin();
    uint32_t diskBlockID = index[*i];
    if(diskBlockID == 0)
    {
        throw Exception("Whoops: there is no index entry for file %u block %u",
            inodeNode.blockNum, fBlockNum);
    }
    boost::scoped_array<uint8_t> block(createBlockBuffer());
    // The first lookup is from the inode.  Subsequent lookups are from
    // the index block, which is loaded into this->block.
    index = reinterpret_cast<uint32_t const*>(block.get());
    // Read the index blocks but not the data block.
    while( distance(i, const_cast<vector<uint32_t> const&>(indices).end()) >= 2 )
    {
        ++i;
        // Load the next index block.
        kfs_disk_read( *this, diskBlockID, block.get() );
        diskBlockID = index[*i];
        if(diskBlockID == 0)
        {
            throw Exception("Internal error: File %u data ends prematurely. "
                "There is no index entry for block %u",
                inodeNode.blockNum, fBlockNum);
        }
    }
    return diskBlockID;
}
